// Time:  O(n)
// Space: O(1)

// g++ -o test_reverse_list reverse-linked-list.cpp -std=c++11

#include "head/ListNode.h"
#include <iostream>
#include <vector>


class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        auto dummy = ListNode{0};

        while (head) {
            auto tmp = head->next;
            head->next = dummy.next;
            dummy.next = head;
            head = tmp;
        }

        return dummy.next;
    }
};

void printList(ListNode* head) {
    while (head) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

ListNode* buildList(const std::vector<int>& values) {
    if (values.empty()) {
        return nullptr;
    }
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    for (size_t i = 1; i < values.size(); ++i) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}


int main() {
    Solution solution;

    std::vector<int> values = {1, 2, 3, 4, 5};
    ListNode* head = buildList(values);

    std::cout << "Original list: ";
    printList(head);

    ListNode* reversedHead = solution.reverseList(head);

    std::cout << "Reversed list: ";
    printList(reversedHead);

    return 0;
}